package com.zlk.algorithm.algorithm.greedy;

import com.zlk.algorithm.dataStructure.tree.NodeUtils;
import org.junit.Test;

import java.util.PriorityQueue;

/**
 * @program: algorithm
 * @ClassName LessMoneySplitGold
 * @description:一块金条切成两半，是需要花费和长度数值一样的铜板
 * 比如长度为20的金条，不管怎么切都要花费20个铜板，一群人想整分整块金条，怎么分最省铜板?
 * 例如，给定数组{10,20,30}，代表一共三个人，整块金条长度为60，金条要分成10，20，30三个部分。
 * 如果先把长度60的金条分成10和50，花费60；再把长度50的金条分成20和30，花费50；一共花费110铜板
 * 但如果先把长度60的金条分成30和30，花费60；再把长度30金条分成10和20，花费30；一共花费90铜板
 * 输入一个数组，返回分割的最小代价
 * @author: slfang
 * @create: 2024-02-27 14:08
 * @Version 1.0
 **/
public class LessMoneySplitGold {

    @Test
    public void test(){
        int testTime = 100000;
        int maxSize = 6;
        int maxValue = 1000;
        for (int i = 0; i < testTime; i++) {
            int[] arr = NodeUtils.enerateRandomArray(maxSize, maxValue);
            if (lessMoney1(arr) != lessMoney2(arr)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }

    private int lessMoney2(int[] arr) {
        return process(arr,0);
    }

    private int process(int[] arr,int pre) {
        if (arr.length == 1) {
            return pre;
        }
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                ans = Math.min(process(copyAndMergeTwo(arr,i,j),pre),ans);
            }
        }
        return ans;
    }

    public static int[] copyAndMergeTwo(int[] arr, int i, int j) {
        int[] ans = new int[arr.length - 1];
        int ansi = 0;
        for (int arri = 0; arri < arr.length; arri++) {
            if (arri != i && arri != j) {
                ans[ansi++] = arr[arri];
            }
        }
        ans[ansi] = arr[i] + arr[j];
        return ans;
    }

    int lessMoney1(int[] arr){
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            priorityQueue.add(arr[i]);
        }
        int cost = 0;
        int total = 0;
        while (priorityQueue.size()!=1){
            Integer poll1 = priorityQueue.poll();
            Integer poll2 = priorityQueue.poll();
            total = poll1+poll2;
            cost+= total;
            priorityQueue.add(total);
        }
        return cost;
    }




}
